public class line_tree{
    static int n = 10; // n是元素个数
    static int[] array = {0, 1, 5, 1, 3, 4, 2, 0, 9, 0, 9};
    // array是原序列(第一个0是占array[0]位的)
    static Node[] tree = new Node[4*n]; // tree是线段树
    
    public static void main(String[] args) {
        initTree();
        build(1, 10, 1); // 利用build函数建树
        System.out.println("操作1：[2，5]的区间和是：" + query(2, 5, 1));
        // 利用query函数搜索区间和
        modify(5, 9, 1); // 利用modify函数实现单点修改（元素5从4改为9）
        System.out.println("操作2：元素5从4改为9，此时[2，5]的区间和是：" + query(2, 5, 1));
        modifySegment(3, 4, 3, 1);
        // 利用modifySegment函数将[3，4]每个元素增加3
        System.out.println("操作3：区间[3，4]每个元素+3，此时[2，5]的区间和是：" + query(2, 5, 1));
    }
    
    static void initTree (){
        for(int i = 0; i < tree.length; i++){
            tree[i] = new Node(0, 0, 0, 0);
        }
    }
    
    static void updateNode (int num) { // num是当前节点序号
        tree[num].sum = tree[num * 2].sum + tree[num * 2 + 1].sum;
    }
    
    static void build (int l, int r, int num) { // 建树
        tree[num].l = l;
        tree[num].r = r;
        if (l == r) { // l = r说明到达叶子节点
            tree[num].sum = array[l];
            return;
        }
        int mid = (l + r) / 2;
        build(l, mid, num * 2); // 递归左儿子
        build(mid + 1, r, num * 2 + 1); // 递归右儿子
        updateNode(num);
    }
    
    static void modify (int i, int value, int num) { // 把元素i修改为值value
        if (tree[num].l == tree[num].r) { // 到达叶子节点
            tree[num].sum = value;
            return;
        }
        int mid = (tree[num].l + tree[num].r) / 2;
        if (i <= mid) {
            modify(i, value, num * 2); // 递归左儿子
        }
        else {
            modify(i, value, num * 2 + 1); // 递归右儿子
        }
        updateNode(num);
    }
    
    static void modifySegment(int l, int r, int value, int num) { // [l,r]每一项都增加value
        if (tree[num].l == l && tree[num].r == r) { // 找到当前区间
            tree[num].sum += ( r - l + 1 ) * value; // r-l+1是区间元素个数
            tree[num].lazy += value;
            return;
        }
        int mid = (tree[num].l + tree[num].r) / 2;
        if (r <= mid) { // 在左区间
            modifySegment(l, r, value, num * 2);
        }
        else if (l > mid) { // 在右区间
            modifySegment(l, r, value, num * 2 + 1);
        }
        else { // 分成2块
            modifySegment(l, mid, value, num * 2);
            modifySegment(mid + 1, r, value, num * 2 + 1);
        }
        updateNode(num);
    }
    
    static void pushDown(int num) {
        if(tree[num].l == tree[num].r) { // 叶节点不用下传标记
            tree[num].lazy = 0; // 清空当前标记
            return;
        }
        tree[num * 2].lazy += tree[num].lazy; // 下传左儿子的懒惰标记
        tree[num * 2 + 1].lazy += tree[num].lazy; // 下传右儿子的懒惰标记
        tree[num * 2].sum += (tree[num * 2].r - tree[num * 2].l + 1) * tree[num].lazy; // 更新左儿子的值
        tree[num * 2 + 1].sum += (tree[num * 2 + 1].r - tree[num * 2 + 1].l + 1) * tree[num].lazy; // 更新右儿子的值
        tree[num].lazy=0; // 清空当前节点的懒惰标记
    }
    
    static int query (int l, int r, int num) {
        if (tree[num].lazy != 0) { // 下传懒惰标记
            pushDown(num);
        }
        if (tree[num].l == l && tree[num].r == r) { // 找到当前区间
            return tree[num].sum;
        }
        int mid = (tree[num].l + tree[num].r) / 2;
        if (r <= mid) { // 在左区间
            return query(l, r, num * 2);
        }
        if (l > mid) { // 在右区间
            return query(l, r, num * 2 + 1);
        }
        return query(l, mid, num * 2) + query(mid + 1, r, num * 2 + 1); // 分成2块
    }
    
    static class Node {
        int l; // l是区间左边界
        int r; // r是区间右边界
        int sum; // sum是区间元素和
        int lazy; // lazy是懒惰标记
    
        public Node (int l, int r, int sum, int lazy){
            this.l = l;
            this.r = r;
            this.sum = sum;
            this.lazy = lazy;
        }
    }
}

